{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #矩阵中的最长递增路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort #memoization #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序 #记忆化搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestIncreasingPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中的最长递增路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<code>m x n</code> 整数矩阵&nbsp;<code>matrix</code> ，找出其中 <strong>最长递增路径</strong> 的长度。</p>\n",
    "\n",
    "<p>对于每个单元格，你可以往上，下，左，右四个方向移动。 <strong>不能</strong> 在 <strong>对角线</strong> 方向上移动或移动到 <strong>边界外</strong>（即不允许环绕）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg\" style=\"width: 242px; height: 242px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[9,9,4],[6,6,8],[2,1,1]]\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>最长递增路径为&nbsp;<code>[1, 2, 6, 9]</code>。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg\" style=\"width: 253px; height: 253px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[3,4,5],[3,2,6],[2,2,1]]\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>最长递增路径是&nbsp;<code>[3, 4, 5, 6]</code>。注意不允许在对角线方向上移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt;= matrix[i][j] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 329&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/\">https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fpTFWP](https://leetcode.cn/problems/fpTFWP/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fpTFWP](https://leetcode.cn/problems/fpTFWP/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[9,9,4],[6,6,8],[2,1,1]]', '[[3,4,5],[3,2,6],[2,2,1]]', '[[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.m = 0\n",
    "        self.n = 0\n",
    "        self.matrix = None\n",
    "        self.max = 0\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        self.matrix = matrix\n",
    "        self.m = len(matrix)\n",
    "        self.n = len(matrix[0])\n",
    "        dp = [[-1 for _ in range(self.n)] for _ in range(self.m)]\n",
    "        for i in range(0, self.m):\n",
    "            for j in range(0, self.n):\n",
    "                self.f(i, j,dp)\n",
    "\n",
    "        return self.max\n",
    "\n",
    "    def f(self, i: int, j: int,dp : List[List[int]]) -> int:\n",
    "        if dp[i][j] != -1:\n",
    "            return dp[i][j]\n",
    "        length = 0\n",
    "        if i - 1 >= 0 and self.matrix[i][j] < self.matrix[i - 1][j]:\n",
    "            length = max(length, self.f(i - 1, j,dp))\n",
    "        if i + 1 < self.m and self.matrix[i][j] < self.matrix[i + 1][j]:\n",
    "            length = max(length, self.f(i + 1, j,dp))\n",
    "        if j - 1 >= 0 and self.matrix[i][j] < self.matrix[i][j - 1]:\n",
    "            length = max(length, self.f(i, j - 1,dp))\n",
    "        if j + 1 < self.n and self.matrix[i][j] < self.matrix[i][j + 1]:\n",
    "            length = max(length, self.f(i, j + 1,dp))\n",
    "        self.max = max(self.max, length + 1)\n",
    "        dp[i][j] = length + 1\n",
    "        return length + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        memo = [[0] * n for _ in range(m)]\n",
    "        def dfs(x: int, y: int):\n",
    "            if memo[x][y] != 0: return memo[x][y]\n",
    "            memo[x][y] = 1\n",
    "            for new_x, new_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and matrix[new_x][new_y] > matrix[x][y]:\n",
    "                    memo[x][y] = max(memo[x][y], dfs(new_x, new_y) + 1) # 关键\n",
    "            return memo[x][y]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        def dfs(a: int, b: int, path: list[tuple[int, int]]) -> int:\n",
    "            if -1 != dp[a][b]:\n",
    "                return dp[a][b]\n",
    "            a_1, b_1, a1, b1 = a - 1, b - 1, a + 1, b + 1\n",
    "            new_path = path + [(a, b)]\n",
    "            res = 1\n",
    "            if -1 < a_1 and matrix[a_1][b] < matrix[a][b] and (a_1, b) not in path:\n",
    "                res = max(res, 1 + dfs(a = a_1, b = b, path = new_path))\n",
    "            if -1 < b_1 and matrix[a][b_1] < matrix[a][b] and (a, b_1) not in path:\n",
    "                res = max(res, 1 + dfs(a = a, b = b_1, path = new_path))\n",
    "            if a1 < m and matrix[a1][b] < matrix[a][b] and (a1, b) not in path:\n",
    "                res = max(res, 1 + dfs(a = a1, b = b, path = new_path))\n",
    "            if b1 < n and matrix[a][b1] < matrix[a][b] and (a, b1) not in path:\n",
    "                res = max(res, 1 + dfs(a = a, b = b1, path = new_path))\n",
    "            return res\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[-1 for _j in range(n)] for _i in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = dfs(a = i, b = j, path = [])\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        record=[[None for j in range(n)] for i in range(m)]\n",
    "        def dfs(i,j):\n",
    "            if not record[i][j]:\n",
    "                temp=[1]\n",
    "                if i>0 and matrix[i][j]>matrix[i-1][j]:temp.append(dfs(i-1,j)+1)\n",
    "                if i<m-1 and matrix[i][j]>matrix[i+1][j]:temp.append(dfs(i+1,j)+1)\n",
    "                if j>0 and matrix[i][j]>matrix[i][j-1]:temp.append(dfs(i,j-1)+1)\n",
    "                if j<n-1 and matrix[i][j]>matrix[i][j+1]:temp.append(dfs(i,j+1)+1)\n",
    "                record[i][j]=max(temp)\n",
    "            return record[i][j]\n",
    "        res=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dfs(i,j)>res:\n",
    "                    res=dfs(i,j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self , matrix: List[List[int]]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if not dp[i][j]:\n",
    "                val = matrix[i][j]\n",
    "                dp[i][j] = 1 + max(\n",
    "                        dfs(i-1, j) if i and val<matrix[i-1][j] else 0,\n",
    "                        dfs(i+1, j) if i< m-1 and val<matrix[i+1][j] else 0,\n",
    "                        dfs(i, j-1) if j and val< matrix[i][j-1] else 0,\n",
    "                        dfs(i, j+1) if j< n-1 and val<matrix[i][j+1] else 0\n",
    "                    )\n",
    "                    \n",
    "            return dp[i][j]\n",
    "        return max(dfs(x,y) for x in range(m) for y in range(n))\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef longestIncreasingPath(self, matrix):\n",
    "\t\tm = len(matrix)\n",
    "\t\tn = len(matrix[0])\n",
    "\t\tq = []\n",
    "\t\tcnt = [[1] * n for _ in range(m)]\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tfor j in range(n):\n",
    "\t\t\t\tq.append([matrix[i][j], i, j])\n",
    "\t\tq.sort()\n",
    "\t\tfor v, i, j in q:\n",
    "\t\t\tfor dx, dy in [[1,0], [0,1], [-1,0], [0,-1]]:\n",
    "\t\t\t\tx1 = i + dx\n",
    "\t\t\t\ty1 = j + dy\n",
    "\t\t\t\tif 0 <= x1 < m and 0 <= y1 < n and v > matrix[x1][y1]:\n",
    "\t\t\t\t\tcnt[i][j] = max(cnt[i][j], cnt[x1][y1] + 1)\n",
    "\t\treturn max([max(row) for row in cnt])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pos = list((i, j) for i in range(n) for j in range(m))\n",
    "        ans = 1\n",
    "        dp = [[1] * m for _ in range(n)]\n",
    "        pos.sort(key = lambda x: matrix[x[0]][x[1]])\n",
    "        for i, j in pos:\n",
    "            for ni, nj in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                if ni < 0 or ni >= n or nj < 0 or nj >= m or matrix[ni][nj] <= matrix[i][j]:\n",
    "                    continue\n",
    "                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1)\n",
    "            ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_round(self, matrix, i, j):\n",
    "        res = []\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x = matrix[i][j]\n",
    "        if i > 0 and matrix[i - 1][j] > x: res.append((i - 1, j))\n",
    "        if j > 0 and matrix[i][j - 1] > x: res.append((i, j - 1))\n",
    "        if i < m - 1 and matrix[i + 1][j] > x: res.append((i + 1, j))\n",
    "        if j < n - 1 and matrix[i][j + 1] > x: res.append((i, j + 1))\n",
    "        return res\n",
    "\n",
    "    def dfs(self, matrix: List[List[int]], i: int, j: int):\n",
    "        if (i, j) in self.d:\n",
    "            return self.d[(i, j)]\n",
    "        deep=1\n",
    "        for k, t in self.get_round(matrix, i, j):\n",
    "            deep = max(deep, self.dfs(matrix, k, t) + 1)\n",
    "        self.d[(i, j)] = deep\n",
    "        return deep\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        ret = 1\n",
    "        self.d = {}\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                ret = max(ret, self.dfs(matrix, i, j))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        x_y_ele = []\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x_y_ele.append([i,j,matrix[i][j]])\n",
    "        def takeThird(ele):\n",
    "            return ele[2]\n",
    "        x_y_ele.sort(key=takeThird)\n",
    "\n",
    "        minNum = x_y_ele[0][2]\n",
    "        maxNum = x_y_ele[-1][2]\n",
    "        result = 1\n",
    "\n",
    "        for pixel in x_y_ele:\n",
    "            x = pixel[0]\n",
    "            y = pixel[1]\n",
    "            num = pixel[2]\n",
    "\n",
    "            if num == minNum:\n",
    "                dp[x][y] = 1\n",
    "                continue\n",
    "\n",
    "            if x+1 < m and matrix[x+1][y] < matrix[x][y]:\n",
    "                dp[x][y] = max(dp[x][y], dp[x+1][y] + 1)\n",
    "                result = max(result, dp[x][y])\n",
    "\n",
    "            if x-1 >= 0 and matrix[x-1][y] < matrix[x][y]:\n",
    "                dp[x][y] = max(dp[x][y], dp[x-1][y] + 1)\n",
    "                result = max(result, dp[x][y])\n",
    "\n",
    "            if y+1 < n and matrix[x][y+1] < matrix[x][y]:\n",
    "                dp[x][y] = max(dp[x][y], dp[x][y+1] + 1)\n",
    "                result = max(result, dp[x][y])\n",
    "\n",
    "            if y-1 >= 0 and matrix[x][y-1] < matrix[x][y]:\n",
    "                dp[x][y] = max(dp[x][y], dp[x][y-1] + 1)\n",
    "                result = max(result, dp[x][y])\n",
    "\n",
    "        print(dp)\n",
    "        return result\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        pathLen = [1]*(m*n)\n",
    "        digree = [0]*(m*n)\n",
    "        graph = dict()\n",
    "        for i in range(m*n):\n",
    "            graph[i] = []\n",
    "        for row in matrix:\n",
    "            row.append(-1)\n",
    "        matrix.append([-1]*(n+1)) # matrix[-1][-1] == -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = n*i+j\n",
    "                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                    nidx = n*x+y\n",
    "                    if matrix[x][y] > matrix[i][j]:\n",
    "                        graph[idx].append(nidx)\n",
    "                        digree[nidx] += 1\n",
    "        que = []\n",
    "        for idx in range(m*n):\n",
    "            if digree[idx] == 0:\n",
    "                que.append(idx)\n",
    "        rst = 0\n",
    "        while len(que) != 0:\n",
    "            nque = []\n",
    "            for idx in que:\n",
    "                for nidx in graph[idx]:\n",
    "                    digree[nidx] -= 1\n",
    "                    if digree[nidx] == 0:\n",
    "                        nque.append(nidx)\n",
    "            que = nque\n",
    "            rst += 1\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n, mn = len(matrix), len(matrix[0]), len(matrix) * len(matrix[0])\n",
    "        neighbors, degs = [[] for _ in range(mn)], [0] * mn\n",
    "        steps = [(0, 1), (1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for stepi, stepj in steps:\n",
    "                    ii, jj = i + stepi, j + stepj\n",
    "                    if ii < m and jj < n:\n",
    "                        if matrix[i][j] < matrix[ii][jj]:\n",
    "                            neighbors[ii * n + jj].append(i * n + j)\n",
    "                            degs[i * n + j] += 1\n",
    "                        elif matrix[i][j] > matrix[ii][jj]:\n",
    "                            neighbors[i * n + j].append(ii * n + jj)\n",
    "                            degs[ii * n + jj] += 1\n",
    "                        else:\n",
    "                            continue\n",
    "        lens = [0] * mn\n",
    "        q = deque()\n",
    "        for i in range(mn):\n",
    "            if degs[i] == 0:\n",
    "                lens[i] = 1\n",
    "                q.append(i)\n",
    "        while len(q) > 0:\n",
    "            i = q.popleft()\n",
    "            for j in neighbors[i]:\n",
    "                lens[j] = max(lens[j], lens[i] + 1)\n",
    "                degs[j] -= 1\n",
    "                if degs[j] == 0:\n",
    "                    q.append(j)\n",
    "        ans = 0\n",
    "        for i in lens:\n",
    "            ans = max(ans, i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[-1]*n for _ in range(m)]\n",
    "        ret = 0\n",
    "        def dfs(x, y):\n",
    "            if dp[x][y] > -1: return\n",
    "            nonlocal ret\n",
    "            r = 0\n",
    "            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                cx, cy = x+dx, y+dy\n",
    "                if 0<=cx<m and 0<=cy<n and matrix[cx][cy]>matrix[x][y]:\n",
    "                    if dp[cx][cy] == -1:\n",
    "                        dfs(cx, cy)\n",
    "                    c = dp[cx][cy]\n",
    "                    if c > r: r = c\n",
    "            r += 1\n",
    "            if r > ret: ret = r\n",
    "            dp[x][y] = r\n",
    "            return\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(i, j)\n",
    "                \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        rows = len(matrix)\n",
    "        columns = len(matrix[0])\n",
    "        longest_increasing_path_matrix = [0] * rows\n",
    "        for index in range(rows):\n",
    "            longest_increasing_path_matrix[index] = [0] * columns\n",
    "        answer = 0\n",
    "        for row in range(rows):\n",
    "            for column in range(columns):\n",
    "                answer = max(answer, dfs(matrix, longest_increasing_path_matrix, rows, columns, row, column, -1))\n",
    "        return answer\n",
    "\n",
    "def dfs(matrix, longest_increasing_path_matrix, rows, columns, row, column, pre_val):\n",
    "    if row < 0 or row >= rows or column < 0 or column >= columns or pre_val >= matrix[row][column]:\n",
    "        return 0\n",
    "    if longest_increasing_path_matrix[row][column]:        # 记忆化搜索，记录已经访问过节点的最长增减路径值\n",
    "        return longest_increasing_path_matrix[row][column]\n",
    "    dy = [0, -1, 0, 1]\n",
    "    dx = [1, 0, -1, 0]\n",
    "    for index in range(4):\n",
    "        longest_increasing_path_matrix[row][column] = max(longest_increasing_path_matrix[row][column], dfs(matrix, longest_increasing_path_matrix, rows, columns, row + dy[index], column + dx[index], matrix[row][column]) + 1)\n",
    "    return longest_increasing_path_matrix[row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        self.rows = len(matrix)\n",
    "        self.cols = len(matrix[0])\n",
    "        # dfs+dp\n",
    "        lengths = [[0 for _ in range(self.cols)] for _ in range(self.rows)]\n",
    "        for r in range(self.rows):\n",
    "            for c in range(self.cols):\n",
    "                res_temp = self.dfs(r, c, matrix, 1, lengths)\n",
    "                res = max(res, res_temp)\n",
    "        print(lengths)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, row, col, matrix, length, lengths):\n",
    "        if lengths[row][col]>0:\n",
    "            return lengths[row][col]\n",
    "\n",
    "        dx = [0, 0, 1, -1]\n",
    "        dy = [1, -1, 0, 0]\n",
    "        length_new = length\n",
    "        for i in range(4):\n",
    "            row_new = row+dx[i]\n",
    "            col_new = col+dy[i]\n",
    "            if (0<=row_new<self.rows) and (0<=col_new<self.cols) and (matrix[row_new][col_new]>matrix[row][col]):\n",
    "                length_new = max(length_new, self.dfs(row_new, col_new, matrix, 1, lengths) + 1)\n",
    "\n",
    "        lengths[row][col] = length_new\n",
    "        \n",
    "        return length_new\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix) + 2, len(matrix[0]) + 2\n",
    "        default = -1\n",
    "        grid = [[default] * n] + [[default] + x + [default] for x in matrix] + [[default] * n]\n",
    "        xn = [1, 0, -1, 0]\n",
    "        yn = [0, 1, 0, -1]\n",
    "\n",
    "        dp = [[0] * n for i in range(m)]\n",
    "\n",
    "        def refresh(i, j, v, last):\n",
    "            if last < grid[i][j] and v > dp[i][j]:\n",
    "                dp[i][j] = v\n",
    "                for k in range(4):\n",
    "                    refresh(i + xn[k], j + yn[k], v + 1, grid[i][j])\n",
    "        \n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                flag = True\n",
    "                for k in range(4):\n",
    "                    c = grid[i + xn[k]][j + yn[k]]\n",
    "                    if c < grid[i][j] and c >= 0:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    refresh(i, j, 1, -1)\n",
    "\n",
    "        return max(dp[i][j] for i in range(1, m - 1) for j in range(1, n - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        memo = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(i,j):\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "            else:\n",
    "                memo[i][j] = 1\n",
    "                for dirct in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                    new_i,new_j = i+dirct[0],j+dirct[1]\n",
    "                    if 0<=new_i<m and 0<=new_j<n and matrix[new_i][new_j]>matrix[i][j]:\n",
    "                        memo[i][j] = max(memo[i][j],dfs(new_i,new_j)+1)\n",
    "            return memo[i][j]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,dfs(i,j))\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        row, column = len(matrix), len(matrix[0])\n",
    "        cache = [[0]*column for _ in range(row)]\n",
    "        max_length= 0\n",
    "        def dfs(i,j):\n",
    "            if cache[i][j]!=0:\n",
    "                return cache[i][j]\n",
    "            for di,dj in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "                ni,nj = i+di, j+dj\n",
    "                if 0<=ni<row and 0<=nj<column and matrix[i][j]<matrix[ni][nj]:\n",
    "                    cache[i][j] = max(cache[i][j],dfs(ni,nj))\n",
    "            cache[i][j] += 1\n",
    "            return cache[i][j]\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                length = dfs(i,j)\n",
    "                if length>max_length:\n",
    "                    max_length=length\n",
    "        return max_length\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            res = 0\n",
    "            for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] < grid[i][j]:\n",
    "                    res = max(res, dfs(ni, nj))\n",
    "            return res + 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        res = 1\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            l = 1\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                newi, newj = i+di, j+dj\n",
    "                if 0<=newi<m and 0<=newj<n and matrix[newi][newj] > matrix[i][j]:\n",
    "                    l = max(l, dfs(newi, newj) + 1)\n",
    "            return l\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j , m, n):\n",
    "            best = 1\n",
    "            dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "            for dx, dy in dirs:\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:\n",
    "                    best = max(best, dfs(x, y, m, n) + 1)\n",
    "            return best\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dfs(i, j, m ,n))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, column: int) -> int:\n",
    "            best = 1\n",
    "            for dx, dy in Solution.DIRS:\n",
    "                newRow, newColumn = row + dx, column + dy\n",
    "                if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:\n",
    "                    best = max(best, dfs(newRow, newColumn) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if matrix==[]:\n",
    "            return 0\n",
    "        @lru_cache(None)\n",
    "        def f(i,j):\n",
    "            max_ = 1\n",
    "            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=x<m and 0<=y<n and matrix[x][y]>matrix[i][j]:\n",
    "                    max_ = max(max_, f(x,y)+1)\n",
    "            return max_\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,f(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) :\n",
    "        self.n = 0\n",
    "        self.m = 0\n",
    "        self.dx = [0, 1, 0, -1]\n",
    "        self.dy = [1, 0, -1, 0]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        self.n = len(matrix)\n",
    "        self.m = len(matrix[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(x: int, y: int) ->int:\n",
    "            s = 1\n",
    "            for i in range(4):\n",
    "                xx = x + self.dx[i]\n",
    "                yy = y + self.dy[i]\n",
    "                if 0 <= xx < self.n and 0 <= yy < self.m and matrix[xx][yy] > matrix[x][y]:\n",
    "                    s = max(s, dfs(xx, yy) + 1)\n",
    "            return s\n",
    "\n",
    "        ans  = 1\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.m):\n",
    "                ans = max(ans,dfs(i, j))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        pos = ((0, -1), (0, 1), (-1, 0), (1, 0))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            res = 1\n",
    "            for dx, dy in pos:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and matrix[x][y] < matrix[nx][ny]:\n",
    "                    res = max(res, dfs(nx, ny) + 1)\n",
    "            return res\n",
    "        dfs.cache_clear()\n",
    "        return max(dfs(i, j) for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        dct={}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in ((i+1,j),(i-1,j),(i,j-1),(i,j+1)):\n",
    "                    if not 0<=x<m or not 0<=y<n:\n",
    "                        continue\n",
    "                    if matrix[i][j]<matrix[x][y]:\n",
    "                        if (i,j) not in dct:\n",
    "                            dct[(i,j)]=[(x,y)]\n",
    "                        else:\n",
    "                            dct[(i,j)].append((x,y))\n",
    "        mat=[[0]*n for _ in range(m)]\n",
    "        stack=[]\n",
    "        val=set()\n",
    "        print(dct)\n",
    "        for lst in dct.values():\n",
    "            for v in lst:\n",
    "                val.add(v)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i,j) not in val:\n",
    "                    stack.append((i,j,1))\n",
    "        while stack:\n",
    "            for _ in range(len(stack)):\n",
    "                cur=stack.pop()\n",
    "                x,y,k=cur\n",
    "                if mat[x][y]>=k:\n",
    "                    \n",
    "                    continue \n",
    "                mat[x][y]=k     \n",
    "                if (x,y) not in dct:\n",
    "                    continue\n",
    "                \n",
    "                for i,j in dct[(x,y)]:\n",
    "                    stack.append([i,j,k+1])\n",
    "        return max([max(mat[i]) for i in range(m)])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        movements = [(0, -1), (0, 1), (1, 0), (-1, 0)]\n",
    "        visited = {}\n",
    "        d = collections.deque()\n",
    "        ans = 1\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if (x, y) not in visited:\n",
    "               visited[(x, y)] = 1\n",
    "            else:\n",
    "                return visited[(x, y)]\n",
    "            cur = matrix[x][y]\n",
    "            for move in movements:\n",
    "                x_next, y_next = x+move[0], y+move[1]\n",
    "                if x_next >=0 and x_next < n and y_next >=0 and y_next < m:\n",
    "                    if matrix[x_next][y_next] > cur:\n",
    "                        if (x_next, y_next) in visited:\n",
    "                            visited[(x, y)] = max(visited[(x, y)], visited[(x_next, y_next)]+1)\n",
    "                        else:\n",
    "                            visited[(x, y)] = max(visited[(x, y)], dfs(x_next, y_next) + 1)\n",
    "            \n",
    "            return visited[(x, y)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def getcnt(i,j):\n",
    "            max_cnt = 0\n",
    "            for x, y in ((0,1),(0,-1),(1,0),(-1,0)):\n",
    "                new_i, new_j = i+x, j+y\n",
    "                if new_i < 0 or new_i >= m or new_j < 0 or new_j >= n:\n",
    "                    continue\n",
    "                if matrix[new_i][new_j] > matrix[i][j]:\n",
    "                    old_value = matrix[i][j]\n",
    "                    matrix[i][j] = 0\n",
    "                    cnt = getcnt(new_i,new_j)+1\n",
    "                    matrix[i][j] = old_value\n",
    "                    if cnt > max_cnt:\n",
    "                            max_cnt = cnt\n",
    "            return max_cnt\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        max_len = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                    cnt = getcnt(i,j)+1\n",
    "                    if cnt > max_len:\n",
    "                        max_len = cnt\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        delta = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        N = len(matrix)\n",
    "        M = len(matrix[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(row,col):\n",
    "            step_best = 1\n",
    "            for dx,dy in delta:\n",
    "                row_new,col_new = row + dx,col + dy\n",
    "                if 0<=row_new<N and 0<=col_new<M:\n",
    "                    if matrix[row_new][col_new] > matrix[row][col]:\n",
    "                        step_best = max(step_best,dfs(row_new,col_new)+1)\n",
    "            return step_best\n",
    "        \n",
    "        res = 1\n",
    "        for row in range(N):\n",
    "            for col in range(M):\n",
    "                res = max(res,dfs(row,col))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache \n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            cnt = 1\n",
    "            for dx, dy in dirs:\n",
    "                if 0 <= x+dx and x+dx < m and 0 <= y+dy and y+dy < n and matrix[x][y] < matrix[x+dx][y+dy]:\n",
    "                    cnt = max(cnt, 1 + dfs(x+dx, y+dy))\n",
    "            return cnt\n",
    "        maxl = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                maxl = max(maxl, dfs(i, j))\n",
    "        return maxl\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dirs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, col: int) -> int:\n",
    "            res = 1\n",
    "            for dx,dy in self.dirs:\n",
    "                next_r, next_c = row + dx, col + dy\n",
    "                if 0 <= next_r < rows and 0 <= next_c < cols and matrix[next_r][next_c] > matrix[row][col]:\n",
    "                    res = max(res, dfs(next_r,next_c) + 1)\n",
    "            return res\n",
    "        res = 0\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                res = max(res,dfs(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            res = 1\n",
    "            for dx,dy in [(0,-1),(0,1),(1,0),(-1,0)]:\n",
    "                if 0<=x+dx<m and 0<=y+dy<n and matrix[x+dx][y+dy]>matrix[x][y]:\n",
    "                    res = max(res,1+dfs(x+dx,y+dy))\n",
    "            return res\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,dfs(i,j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        # 最长递增路径，其实找每个位置的最长递减路径也一样。\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y ):\n",
    "            best = 1\n",
    "            for i, j in directions:\n",
    "                nx, ny = x + i, y + j\n",
    "                if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] > matrix[x][y]:\n",
    "                    best = max(dfs(nx, ny) + 1, best)\n",
    "            return best\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            longest = 1\n",
    "            for di, dj in dirs:\n",
    "                ni, nj = di + i, dj + j\n",
    "                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:\n",
    "                    longest = max(longest, dfs(ni, nj) + 1)\n",
    "\n",
    "            return longest\n",
    "\n",
    "        res = 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i , j))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dirs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, col: int) -> int:\n",
    "            res = 1\n",
    "            for dx,dy in Solution.dirs:\n",
    "                next_r, next_c = row + dx, col + dy\n",
    "                if 0 <= next_r < rows and 0 <= next_c < cols and matrix[next_r][next_c] > matrix[row][col]:\n",
    "                    res = max(res, dfs(next_r,next_c) + 1)\n",
    "            return res\n",
    "        res = 0\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                res = max(res,dfs(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dirs = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, col: int) -> int:\n",
    "            res = 1\n",
    "            for dx,dy in Solution.dirs:\n",
    "                next_r, next_c = row + dx, col + dy\n",
    "                if 0 <= next_r < rows and 0 <= next_c < cols and matrix[next_r][next_c] > matrix[row][col]:\n",
    "                    res = max(res, dfs(next_r,next_c) + 1)\n",
    "            return res\n",
    "        res = 0\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                res = max(res,dfs(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        delta = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        N = len(matrix)\n",
    "        M = len(matrix[0])\n",
    "\n",
    "        @lru_cache(2**31)\n",
    "        def dfs(row,col):\n",
    "            step_best = 1\n",
    "            for dx,dy in delta:\n",
    "                row_new,col_new = row + dx,col + dy\n",
    "                if 0<=row_new<N and 0<=col_new<M:\n",
    "                    if matrix[row_new][col_new] > matrix[row][col]:\n",
    "                        step_best = max(step_best,dfs(row_new,col_new)+1)\n",
    "            return step_best\n",
    "        \n",
    "        res = 1\n",
    "        for row in range(N):\n",
    "            for col in range(M):\n",
    "                res = max(res,dfs(row,col))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        directs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        G = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val = matrix[i][j]\n",
    "                for x, y in ((i+1, j), (i, j+1)):\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        if val < matrix[x][y]:\n",
    "                            G[(i, j)].append((x, y))\n",
    "                        elif val > matrix[x][y]:\n",
    "                            G[(x, y)].append((i, j))\n",
    "        \n",
    "        @functools.cache\n",
    "        def max_length(i, j):\n",
    "            ans = 1\n",
    "            for x, y in G[(i, j)]:\n",
    "                ans = max(ans, 1 + max_length(x, y))\n",
    "            return ans\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, max_length(i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        # DFS + 记忆化递归搜索,值记录某个单元格（i，j）的最长递增路径长度\n",
    "        # BFS无法用记忆化搜索，不行，除非转化成有向图的拓扑排序\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dx = [0, -1, 0, 1]\n",
    "        dy = [-1, 0, 1, 0]\n",
    "        # 记忆化递归搜索,值记录某个单元格（i，j）的最长递增路径长度，不要记录depth\n",
    "        @lru_cache(None)  # 设置maxsize=None表示不限制大小，超过会调用LRU删除最近最少使用的哈希记录\n",
    "        def dfs(curr): # 记录从当前节点出发的最长递增路径长度\n",
    "            curr_num = matrix[curr[0]][curr[1]]\n",
    "            best_path = 1\n",
    "            for i in range(4):\n",
    "                nx = curr[0] + dx[i]\n",
    "                ny = curr[1] + dy[i]\n",
    "                if 0<=nx<m and 0<=ny<n and matrix[nx][ny]>curr_num:\n",
    "                    tmp_depth = dfs((nx,ny)) + 1 # 下一节点的最长路径长度，再加一\n",
    "                    best_path = max(best_path, tmp_depth)\n",
    "            return best_path\n",
    "        ret = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ret = max(ret, dfs((i,j))) # （i，j）元组是可哈希的类型\n",
    "        return ret\n",
    "\n",
    "        '''\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                q = collections.deque()\n",
    "                q.append((i, j))\n",
    "                vis = [[False]*n for _ in range(m)]\n",
    "                vis[i][j] = True\n",
    "                curr_path = 0\n",
    "                while q:\n",
    "                    curr_path += 1\n",
    "                    for _ in range(len(q)):\n",
    "                        x, y = q.popleft()\n",
    "                        curr = matrix[x][y]\n",
    "                        for k in range(4): # 注意i，j，k\n",
    "                            nx = x + dx[k]\n",
    "                            ny = y + dy[k]\n",
    "                            if 0<=nx<m and 0<=ny<n and matrix[nx][ny]>curr:\n",
    "                                # vis[nx][ny] = True\n",
    "                                q.append((nx, ny))\n",
    "                inc_path = max(inc_path, curr_path)\n",
    "        return inc_path\n",
    "        '''\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        graph_map = collections.defaultdict(list)\n",
    "\n",
    "        # build path map\n",
    "        for idx in range(len(matrix)):\n",
    "            for idy in range(len(matrix[idx])):\n",
    "                # up\n",
    "                if idx - 1 >= 0 and matrix[idx - 1][idy] > matrix[idx][idy]:\n",
    "                    graph_map[(idx, idy)].append((idx - 1, idy))\n",
    "                # right\n",
    "                if idy + 1 < len(matrix[idx]) and matrix[idx][idy + 1] > matrix[idx][idy]:\n",
    "                    graph_map[(idx, idy)].append((idx, idy + 1))\n",
    "                # down\n",
    "                if idx + 1 < len(matrix) and matrix[idx + 1][idy] > matrix[idx][idy]:\n",
    "                    graph_map[(idx, idy)].append((idx + 1, idy))\n",
    "                # left\n",
    "                if idy - 1 >= 0 and matrix[idx][idy - 1] > matrix[idx][idy]:\n",
    "                    graph_map[(idx, idy)].append((idx, idy - 1))\n",
    "\n",
    "        visited_idx_len_map = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(start_x, start_y):\n",
    "            if (start_x, start_y) in visited_idx_len_map:\n",
    "                return visited_idx_len_map[(start_x, start_y)]\n",
    "\n",
    "            visited_idx_len_map[(start_x, start_y)] += 1\n",
    "            for next_x, next_y in graph_map[(start_x, start_y)]:\n",
    "                visited_idx_len_map[(start_x, start_y)] = max(visited_idx_len_map[(start_x, start_y)],\n",
    "                                                              dfs(next_x, next_y) + 1)\n",
    "            return visited_idx_len_map[(start_x, start_y)]\n",
    "\n",
    "        res = 1\n",
    "        for idx in range(len(matrix)):\n",
    "            for idy in range(len(matrix[idx])):\n",
    "                res = max(res, dfs(idx, idy))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "       m = len(matrix)\n",
    "       n = len(matrix[0])\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i < 0 or i >= m or j < 0 or j >= n:\n",
    "             return 0\n",
    "          res = 1\n",
    "          dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "          for d in dirs:\n",
    "             x = i + d[0]\n",
    "             y = j + d[1]\n",
    "             if x >= 0 and x < m and y >= 0 and y < n and matrix[x][y] > matrix[i][j]:\n",
    "                res = max(res, dfs(x, y) + 1)\n",
    "          return res\n",
    "       res = 0\n",
    "       for i in range(m):\n",
    "          for j in range(n):\n",
    "             res = max(res, dfs(i, j))\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        father_dict = {}\n",
    "        child_dict = {}\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cur = matrix[i][j]\n",
    "                father_dict[(i, j)] = 0\n",
    "                child_dict[(i, j)] = []\n",
    "                if i > 0:\n",
    "                    tmp = matrix[i - 1][j]\n",
    "                    if tmp > cur:\n",
    "                        father_dict[(i, j)] = 1\n",
    "                    elif tmp < cur:\n",
    "                        child_dict[(i, j)].append((i - 1, j))\n",
    "                if i < m - 1:\n",
    "                    tmp = matrix[i + 1][j]\n",
    "                    if tmp > cur:\n",
    "                        father_dict[(i, j)] = 1\n",
    "                    elif tmp < cur:\n",
    "                        child_dict[(i, j)].append((i + 1, j))\n",
    "                if j > 0:\n",
    "                    tmp = matrix[i][j - 1]\n",
    "                    if tmp > cur:\n",
    "                        father_dict[(i, j)] = 1\n",
    "                    elif tmp < cur:\n",
    "                        child_dict[(i, j)].append((i, j - 1))\n",
    "                if j < n - 1:\n",
    "                    tmp = matrix[i][j + 1]\n",
    "                    if tmp > cur:\n",
    "                        father_dict[(i, j)] = 1\n",
    "                    elif tmp < cur:\n",
    "                        child_dict[(i, j)].append((i, j + 1))\n",
    "        \n",
    "\n",
    "        #print(father_dict)\n",
    "        #print(child_dict)\n",
    "\n",
    "        @lru_cache(m * n)\n",
    "        def dfs(node):\n",
    "            if len(child_dict[node]) == 0:\n",
    "                return 1\n",
    "            return max(map(lambda x: dfs(x), child_dict[node])) + 1\n",
    "\n",
    "        max_len = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if father_dict[(i, j)]:\n",
    "                    continue\n",
    "                tmp = dfs((i, j))\n",
    "                if tmp > max_len:\n",
    "                    max_len = tmp\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        max_len = 1\n",
    "        edges = defaultdict(set)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if i - 1 >= 0 :\n",
    "                    if matrix[i-1][j] > matrix[i][j]:\n",
    "                        edges[(i,j)].add((i-1,j))\n",
    "                    elif matrix[i-1][j] < matrix[i][j]:\n",
    "                        edges[(i-1,j)].add((i,j))\n",
    "                if j -1 >= 0:\n",
    "                    if matrix[i][j-1] > matrix[i][j]:\n",
    "                        edges[(i,j)].add((i,j-1))\n",
    "                    elif matrix[i][j-1] < matrix[i][j]:\n",
    "                        edges[(i,j-1)].add((i,j))\n",
    "\n",
    "                if i+1 < rows:\n",
    "                    if matrix[i+1][j] > matrix[i][j]:\n",
    "                        edges[(i,j)].add((i+1,j))\n",
    "                    elif matrix[i+1][j] < matrix[i][j]:\n",
    "                        edges[(i+1,j)].add((i,j))\n",
    "                if j + 1 < cols:\n",
    "                    if matrix[i][j+1] > matrix[i][j]:\n",
    "                        edges[(i,j)].add((i,j+1))\n",
    "                    elif matrix[i][j+1] < matrix[i][j]:\n",
    "                        edges[(i,j+1)].add((i,j))\n",
    "\n",
    "        # print(edges)\n",
    "        mem = dict()\n",
    "        def dfs(n):\n",
    "            if n in mem:\n",
    "                return mem[n]\n",
    "            elif n not in edges:\n",
    "                mem[n] = 1\n",
    "                return 1 \n",
    "            else:\n",
    "                max_len = 1\n",
    "                for p in edges[n]:\n",
    "                    p_len = dfs(p)\n",
    "                    # print(p,p_len)\n",
    "                    mem[p] = p_len\n",
    "                    max_len = max(p_len+1,max_len)\n",
    "                return max_len\n",
    "\n",
    "        for e in edges:\n",
    "            e_len = dfs(e)\n",
    "            max_len = max(max_len, e_len)\n",
    "        return max_len\n",
    "            \n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        move = [(1, 0), (-1,0), (0, 1), (0, -1)]\n",
    "        s = set()\n",
    "        d = {}\n",
    "\n",
    "        def dfs(x, y):\n",
    "            tmp = [1]\n",
    "            for a, b in move:\n",
    "                v = 0\n",
    "                xx, yy = x+a, y+b\n",
    "                if 0 <= xx < m and 0<= yy <n and matrix[xx][yy] > matrix[x][y]:\n",
    "                    s.add((xx, yy))\n",
    "                    if d.get((xx, yy), 0) > 0:\n",
    "                        v = 1 + d.get((xx, yy))\n",
    "                    else:\n",
    "                        v = 1 + dfs(xx, yy)\n",
    "                    tmp.append(v)\n",
    "            d[(x, y)] = max(tmp)\n",
    "            return max(tmp)\n",
    "\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in s:\n",
    "                    res.append(dfs(i, j))\n",
    "        return max(res)\n",
    "\n",
    "             \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        row, coll = len(matrix), len(matrix[0])\n",
    "\n",
    "        # 矩阵中每个顶点的id索引\n",
    "        matrix_id = []\n",
    "        i = 0\n",
    "        while i < row:\n",
    "            matrix_id.append([None,]*coll)\n",
    "            j = 0\n",
    "            while j < coll:\n",
    "                matrix_id[i][j] = str(i)+'x'+str(j)\n",
    "                j += 1\n",
    "            i += 1\n",
    "\n",
    "        # 建图\n",
    "        gragh = dict()\n",
    "        i = 0\n",
    "        while i < row:\n",
    "            j = 0\n",
    "            while j < coll:\n",
    "                center_val = matrix[i][j]\n",
    "                center_id = matrix_id[i][j]\n",
    "                if (i-1 >= 0) and (matrix[i-1][j] > center_val):\n",
    "                    up_id = matrix_id[i-1][j]\n",
    "                    if center_id in gragh.keys():\n",
    "                        gragh[center_id].add(up_id)\n",
    "                    else:\n",
    "                        gragh[center_id] = set([up_id,])\n",
    "                if (i+1 < row) and (matrix[i+1][j] > center_val):\n",
    "                    down_id = matrix_id[i+1][j]\n",
    "                    if center_id in gragh.keys():\n",
    "                        gragh[center_id].add(down_id)\n",
    "                    else:\n",
    "                        gragh[center_id] = set([down_id,])\n",
    "                if (j-1 >= 0) and (matrix[i][j-1] > center_val):\n",
    "                    left_id = matrix_id[i][j-1]\n",
    "                    if center_id in gragh.keys():\n",
    "                        gragh[center_id].add(left_id)\n",
    "                    else:\n",
    "                        gragh[center_id] = set([left_id,])\n",
    "                if (j+1 < coll) and (matrix[i][j+1] > center_val):\n",
    "                    right_id = matrix_id[i][j+1]\n",
    "                    if center_id in gragh.keys():\n",
    "                        gragh[center_id].add(right_id)\n",
    "                    else:\n",
    "                        gragh[center_id] = set([right_id,])\n",
    "                j += 1\n",
    "            i += 1\n",
    "\n",
    "        # print(gragh)\n",
    "\n",
    "        # 获取起点, 终点\n",
    "        vertex = set()\n",
    "        i = 0\n",
    "        while i < row:\n",
    "            j = 0\n",
    "            while j < coll:\n",
    "                vertex.add(matrix_id[i][j])\n",
    "                j += 1\n",
    "            i += 1\n",
    "\n",
    "        indegree_vertex = set()\n",
    "        for indegree in gragh.values():\n",
    "            indegree_vertex = indegree_vertex.union(indegree)\n",
    "        begin_vertex = vertex - indegree_vertex\n",
    "\n",
    "        outdegree_vertex = set(gragh.keys())\n",
    "        end_vertex = vertex - outdegree_vertex\n",
    "\n",
    "        # print('..............................')\n",
    "        # print(begin_vertex)\n",
    "        # print('------------------------------')\n",
    "        # print(end_vertex)\n",
    "\n",
    "        # # 计算最长路径（同时固定起点与终点）\n",
    "        # cache = {}\n",
    "        # def max_distance(b, e):\n",
    "        #     if b not in gragh.keys():\n",
    "        #         if b == e:\n",
    "        #             return 1\n",
    "        #         else:\n",
    "        #             return float('-inf')\n",
    "\n",
    "        #     k = (b, e)\n",
    "        #     if k in cache:\n",
    "        #         rs = cache[k]\n",
    "        #     else:\n",
    "        #         rs = max([max_distance(v, e) for v in gragh[b]]) + 1\n",
    "        #         cache[k] = rs\n",
    "        #     return rs\n",
    "\n",
    "        # 计算最长路径（只是固定起点，到任意终点）\n",
    "        cache = {}\n",
    "        def max_distance(b):\n",
    "            if b not in gragh.keys():\n",
    "                return 1\n",
    "\n",
    "            if b in cache:\n",
    "                rs = cache[b]\n",
    "            else:\n",
    "                rs = max([max_distance(v) for v in gragh[b]]) + 1\n",
    "                cache[b] = rs\n",
    "            return rs\n",
    "\n",
    "        max_step = 1\n",
    "        for b in begin_vertex:\n",
    "            # for e in end_vertex:\n",
    "            max_step = max(max_distance(b), max_step)\n",
    "\n",
    "        return max_step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dic = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        self.temp_dic = {}\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            best = 0\n",
    "            for a, b in self.dic:\n",
    "                new_i, new_j = i + a, j + b\n",
    "                if 0 <= new_i < row and 0 <= new_j < col and matrix[i][j] > matrix[new_i][new_j]:\n",
    "                    if (new_i, new_j) not in self.temp_dic:\n",
    "                        best = max(dfs(new_i, new_j), best)\n",
    "                        self.temp_dic[(new_i, new_j)] = dfs(new_i, new_j)\n",
    "                    else:\n",
    "                        best = max(self.temp_dic[(new_i, new_j)], best)\n",
    "            return best+1\n",
    "        res = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                res = max(dfs(i, j), res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    dx = [0, 1, 0, -1]\n",
    "    dy = [1, 0, -1, 0]\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        self.matrix = matrix\n",
    "        ans = 0\n",
    "        for row in range(len(matrix)):\n",
    "            for col in range(len(matrix[0])):\n",
    "                ans = max(ans, self.dfs(row, col))\n",
    "        return ans\n",
    "        \n",
    "    @lru_cache(None)\n",
    "    def dfs(self, row, col):\n",
    "        best = 1\n",
    "        for ix in range(4):\n",
    "            x = row + self.dx[ix]\n",
    "            y = col + self.dy[ix]\n",
    "\n",
    "            if x >= len(self.matrix) or x < 0 or y >= len(self.matrix[0]) or y < 0:\n",
    "                continue\n",
    "\n",
    "            if self.matrix[x][y] > self.matrix[row][col]:\n",
    "                best = max(best, self.dfs(x, y) + 1)\n",
    "        return best\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        visit = {}\n",
    "        def inarea(i,j):\n",
    "            if 0 <= i < len(matrix) and 0 <= j < len(matrix[0]):\n",
    "                return True\n",
    "            return False\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            nonlocal visit\n",
    "            if (i,j) in visit:\n",
    "                return visit[(i,j)]\n",
    "            visit[(i,j)] = 1\n",
    "            if inarea(i-1,j) and matrix[i-1][j] > matrix[i][j]:\n",
    "                visit[(i,j)] = max(visit[(i,j)], 1 + dfs(i-1,j))\n",
    "            if inarea(i+1,j) and matrix[i+1][j] > matrix[i][j]:\n",
    "                visit[(i,j)] = max(visit[(i,j)], 1 + dfs(i+1,j))\n",
    "            if inarea(i,j-1) and matrix[i][j-1] > matrix[i][j]:\n",
    "                visit[(i,j)] = max(visit[(i,j)], 1 + dfs(i,j-1))\n",
    "            if inarea(i,j+1) and matrix[i][j+1] > matrix[i][j]:\n",
    "                visit[(i,j)] = max(visit[(i,j)], 1 + dfs(i,j+1))\n",
    "            return visit[(i,j)]\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                visit[(i,j)] = dfs(i,j)\n",
    "        ma = 0\n",
    "        for i in visit:\n",
    "            ma = max(ma,visit[i])\n",
    "        return ma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix: return 0\n",
    "        visited = set()\n",
    "        \n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            best = 1\n",
    "            visited.add((i,j))\n",
    "            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                i_next, j_next = i + di, j + dj\n",
    "                if 0 <= i_next < n_row and 0 <= j_next < n_col and matrix[i_next][j_next]>matrix[i][j]:\n",
    "                    best = max(best, dfs(i_next, j_next) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        n_row, n_col = len(matrix), len(matrix[0])\n",
    "        for i in range(n_row):\n",
    "            for j in range(n_col):\n",
    "                if (i, j) in visited: continue\n",
    "                ans = max(ans, dfs(i, j))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.m = None\n",
    "        self.n = None\n",
    "        self.matrix = None\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        self.m = len(matrix)\n",
    "        self.n = len(matrix[0])\n",
    "        self.matrix = matrix\n",
    "        ans = 0\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                tmp = self.dfs(i, j)\n",
    "                if tmp > ans:\n",
    "                    ans = tmp\n",
    "        return ans\n",
    "\n",
    "    @cache\n",
    "    def dfs(self, x, y):\n",
    "        ret_ans = 0\n",
    "        ret_ans = max(\n",
    "            max(self.dfs(x + 1, y), ret_ans) if (self.m > x + 1 >= 0 and self.matrix[x + 1][y] > self.matrix[x][y]) else 0,\n",
    "            max(self.dfs(x - 1, y), ret_ans) if (self.m > x - 1 >= 0 and self.matrix[x - 1][y] > self.matrix[x][y]) else 0,\n",
    "            max(self.dfs(x, y + 1), ret_ans) if (self.n > y + 1 >= 0 and self.matrix[x][y + 1] > self.matrix[x][y]) else 0,\n",
    "            max(self.dfs(x, y - 1), ret_ans) if (self.n > y - 1 >= 0 and self.matrix[x][y - 1] > self.matrix[x][y]) else 0,\n",
    "        )\n",
    "        return ret_ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.x_len = None\n",
    "        self.y_len = None\n",
    "        self.direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        self.matrix = None\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, x, y):\n",
    "        longest = 1\n",
    "        for m_x, m_y in self.direction:\n",
    "            next_x, next_y = x + m_x, y + m_y\n",
    "            if 0 <= next_x < self.x_len and 0 <= next_y < self.y_len and self.matrix[next_x][next_y] > self.matrix[x][\n",
    "                y]:\n",
    "                longest = max(longest, self.dfs(next_x, next_y) + 1)\n",
    "        return longest\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        self.x_len = len(matrix)\n",
    "        self.y_len = len(matrix[0])\n",
    "        self.matrix = matrix\n",
    "\n",
    "        for x in range(self.x_len):\n",
    "            for y in range(self.y_len):\n",
    "                res.append(self.dfs(x, y))\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    #  动态刷新DP表\n",
    "    def longestIncreasingPath(self, matrix: list) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        DP = [[1 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]\n",
    "        flag = True\n",
    "\n",
    "        while flag:\n",
    "            temp = False\n",
    "            # 左上角\n",
    "            for index in range(n):\n",
    "                for jndex in range(m):\n",
    "                    if index - 1 >= 0  and matrix[index-1][jndex] > matrix[index][jndex] and DP[index][jndex] < DP[index-1][jndex] + 1:\n",
    "                        DP[index][jndex] = DP[index-1][jndex] + 1\n",
    "                        temp = True\n",
    "                    if jndex - 1 >= 0 and matrix[index][jndex-1] > matrix[index][jndex] and DP[index][jndex] < DP[index][jndex-1] + 1:\n",
    "                        DP[index][jndex] = DP[index][jndex-1] + 1\n",
    "                        temp = True\n",
    "            # print(np.array(DP))\n",
    "            # 右上角\n",
    "            for index in range(n):\n",
    "                for jndex in range(m-1,-1,-1):\n",
    "                    if index - 1 >= 0 and matrix[index-1][jndex] > matrix[index][jndex] and DP[index][jndex] < DP[index-1][jndex] + 1:\n",
    "                        DP[index][jndex] = DP[index - 1][jndex] + 1\n",
    "                        temp = True\n",
    "\n",
    "                    if jndex + 1 < m and matrix[index][jndex+1] > matrix[index][jndex] and DP[index][jndex] < DP[index][jndex+1] + 1:\n",
    "                        DP[index][jndex] = DP[index][jndex+1] + 1\n",
    "                        temp = True\n",
    "            # 左下角\n",
    "            for index in range(n-1, -1, -1):\n",
    "                for jndex in range(m):\n",
    "                    if index + 1 < n and matrix[index+1][jndex] > matrix[index][jndex] and DP[index][jndex] < DP[index+1][jndex] + 1:\n",
    "                        DP[index][jndex] = DP[index + 1][jndex] + 1\n",
    "                        temp = True\n",
    "                    if jndex - 1 >= 0 and matrix[index][jndex - 1] > matrix[index][jndex] and DP[index][jndex] < DP[index][jndex - 1] + 1:\n",
    "                        DP[index][jndex] = DP[index][jndex - 1] + 1\n",
    "                        temp = True\n",
    "\n",
    "            # 右下角\n",
    "\n",
    "            for index in range(n-1, -1, -1):\n",
    "                for jndex in range(m-1, -1,  -1):\n",
    "                    if index + 1 < n and matrix[index+1][jndex] > matrix[index][jndex] and DP[index][jndex] < DP[index+1][jndex] + 1:\n",
    "                        DP[index][jndex] = DP[index + 1][jndex] + 1\n",
    "                        temp = True\n",
    "\n",
    "            if jndex + 1 < m and matrix[index][jndex + 1] > matrix[index][jndex] and DP[index][jndex] < DP[index][\n",
    "                jndex + 1] + 1:\n",
    "                DP[index][jndex] = DP[index][jndex + 1] + 1\n",
    "                temp = True\n",
    "\n",
    "            flag = temp\n",
    "        # print(np.array(DP))\n",
    "        ans = 0\n",
    "        for index in range(n): ans = max(ans, max(DP[index]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "    \n",
    "        ans = self.longestIncreasingPathBFS(matrix)\n",
    "        return int(ans)\n",
    "    def longestIncreasingPathDFS(self, mat):\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        mx = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mx = max(self.dfs(i, j), mx)\n",
    "        return mx\n",
    "        \n",
    "    def dfs(self, row, col):\n",
    "        m, n = m, n = len(mat), len(mat[0])\n",
    "        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        best = 1\n",
    "        for dh, dw in DIRS:\n",
    "            h, w = row + dh, col + dw\n",
    "            if 0<=h<m and 0<=w < n and mat[h][w] > mat[row][col]:\n",
    "                # best = max(self.dfs(h, w) + 1, best)\n",
    "                value = self.dfs(h, w) + 1\n",
    "                best = max(value, best)\n",
    "        return best\n",
    "        \n",
    "    def longestIncreasingPathBFS(self,mat):\n",
    "        if not mat or len(mat) < 1 or len(mat[0]) < 1:\n",
    "            return 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        mx, DIRS = 0, [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        degrees = np.zeros((m, n))\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for dx, dy in DIRS:\n",
    "                    h, w = i + dx, j+dy\n",
    "                    if 0 <= h < m and 0<=w< n and mat[h][w] < mat[i][j]:\n",
    "                        degrees[i][j] += 1\n",
    "                if degrees[i][j] <= 0:\n",
    "                    queue.append((i, j))\n",
    "        ans = 0\n",
    "        while len(queue):\n",
    "            size = len(queue)\n",
    "            ans += 1\n",
    "            for i in range(size):\n",
    "                row, col = queue.popleft()\n",
    "                for dx,dy in DIRS:\n",
    "                    newRow, newCol = row + dx, col + dy\n",
    "                    if 0<= newRow < m and 0<= newCol<n and mat[newRow][newCol] > mat[row][col]:\n",
    "                        degrees[newRow][newCol] -= 1\n",
    "                        if degrees[newRow][newCol] == 0:\n",
    "                            queue.append((newRow, newCol))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\n",
    "\n",
    "    def __init__(self):\n",
    "       \n",
    "        self.move = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self,i,j,m,n):\n",
    "        max_ = 0\n",
    "        for a,b in self.move:\n",
    "            new_i = a + i\n",
    "            new_j = b + j \n",
    "            if 0 <= new_i < m and 0<= new_j < n  and self.matrix[new_i][new_j] > self.matrix[i][j]:\n",
    "                max_ = max(max_,self.dfs(new_i,new_j,m,n) + 1)\n",
    "            \n",
    "        return max_\n",
    "\n",
    "        pass\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        self.matrix = matrix\n",
    "        max_ = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max_ = max(max_,self.dfs(i,j,m,n) + 1)\n",
    "        return max_\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
